package offer.day32;

import java.util.Arrays;

public class No56Second_FindNumberAppearOnce {
    /*
     * 面试题56：数组中数字出现的次数
     * 题目二；数组中唯一只出现一次的数字
     * 自一个数组中除一个数字只出现一次以外，其他数字都出现了三次。
     * 请找出那个只出现一次的数字
     * https://www.jianshu.com/p/258785bdf416
     *
     * 思路：位运算思想
     * 若一个数字出现了第三次，那么它的二进制标识的每一位（0或1）也出现了三次。
     * 若是将所有出现三次的数字的二进制表示的每一位都分别加起来，那么每一位都能被3整除
     * 那么就只有出现一次的数字不能被3整除，因而求出只出现一次的数字
     *
     *
     * */
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 1, 1, 2, 3, 3, 2};
        No56Second_FindNumberAppearOnce f = new No56Second_FindNumberAppearOnce();
        System.out.println("数组中唯一只出现一次的数字是：" + f.FindNumberAppearOnce(array));
    }

    private int FindNumberAppearOnce(int[] array) {
        if (array == null || array.length < 3) {
            return 0;
        }
        int[] bitSum = new int[32];
        int k = 3;
        for (int i = 0; i < array.length; i++) {
            int index = 1;
            for (int j = 31; j >= 0; j--) {
                System.out.print(array[i] & index);
                if ((array[i] & index) !=0) {
                    bitSum[j]++;
                }
                index <<= 1;
            }
            System.out.println();

        }
        System.out.println(Arrays.toString(bitSum));
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result <<= 1;
            result += bitSum[i] % k;
        }
        return result;
    }
}
